package com.azure.code.tree;

import java.util.LinkedList;

/**
 * https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
 * 297 二叉树的序列化与反序列化
 */
public class SerializeBinaryTree_297 {

    public String NULL = "#";
    public String SEP = ",";
    /**
     * 可以遍历二叉树 空节点 使用 # 补充
     */
    public String serialize(TreeNode root){
         StringBuilder sb = new StringBuilder();
         preSerialize(root,sb);
//         postSerialize(root,sb);
         return sb.toString();
    }

    /**
     * 这里使用前序遍历 也可以使用层序遍历
     */
    void preSerialize(TreeNode root,StringBuilder sb){
        if(root==null){
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        preSerialize(root.left,sb);
        preSerialize(root.right,sb);
    }
    void postSerialize(TreeNode root,StringBuilder sb){
        if(root==null){
            sb.append(NULL).append(SEP);
            return;
        }
        postSerialize(root.left,sb);
        postSerialize(root.right,sb);
        sb.append(root.val).append(SEP);
    }


    public TreeNode deserialize(String data){
        LinkedList<String> nodes = new LinkedList<>();
        for (String s : data.split(SEP)){
            nodes.addLast(s);
        }
        return preDeserialize(nodes);
//        return postDeserialize(nodes);
    }

    TreeNode preDeserialize(LinkedList<String> nodes){
        if(nodes.isEmpty()) return null;
        // 前序遍历 列表最左位置是根节点
        String first = nodes.removeFirst();
        if(first.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = preDeserialize(nodes);
        root.right = preDeserialize(nodes);
        return root;
    }

    TreeNode postDeserialize(LinkedList<String> nodes){
        if(nodes.isEmpty()) return null;
        // 前序遍历 列表最左位置是根节点
        String last = nodes.removeLast();
        if(last.equals(NULL)) return null;
        TreeNode root = new TreeNode(Integer.parseInt(last));
        root.right = postDeserialize(nodes);
        root.left = postDeserialize(nodes);
        return root;
    }
    public static void main(String[] args) {
        String data = new SerializeBinaryTree_297().serialize(TreeNodeBuilder.buildTree1());
        System.out.println(data);
        TreeNode root = new SerializeBinaryTree_297().deserialize(data);
        System.out.println(new SerializeBinaryTree_297().serialize(root));
    }

}
